package main.leetcode.offer.firstround.from51to68;

/**
 * 51.数组中的逆序对
 *
 * <p>在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
 *
 * <p>
 *
 * <p>示例 1:输入: [7,5,6,4] 输出: 5
 *
 * <p>限制：0 <= 数组长度 <= 50000
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class ex51 {
    private int[] aux;

    public static void main(String[] args) {
        System.out.println(new ex51().reversePairs(new int[] {7, 5, 6, 4}));
        System.out.println(new ex51().reversePairs(new int[] {5, 4, 3, 2, 1}));
    }

    public int reversePairs(int[] nums) {
        aux = new int[nums.length];
        return mergeSort(nums, 0, nums.length - 1);
    }

    private int mergeSort(int[] nums, int lo, int hi) {
        if (lo >= hi) return 0;
        int mid = lo + ((hi - lo) >> 1);
        return mergeSort(nums, lo, mid) + mergeSort(nums, mid + 1, hi) + merge(nums, lo, mid, hi);
    }

    private int merge(int[] nums, int lo, int mid, int hi) {
        int i = lo, j = mid + 1;
        int count = 0;
        System.arraycopy(nums, lo, aux, lo, hi - lo + 1);
        for (int k = lo; k <= hi; ++k) {
            if (i > mid) nums[k] = aux[j++];
            else if (j > hi) nums[k] = aux[i++];
            else if (aux[i] <= aux[j]) nums[k] = aux[i++];
            else {
                nums[k] = aux[j++];
                // 比如 456 123，4 > 1、2、3，则5、6也满足
                count += mid - i + 1;
            }
        }
        return count;
    }
}
